The present invention relates to signal processing using matched filters, correlators, convolvers, Fourier analyzers, inverse Fourier analyzers, and more particularly to signal processors which measure the impulse response h, the transfer function H, and coherence function .gamma..sup.2 of two signals y and x in real time. The signals y and x, for example, may be the received and transmitted signals in a radar, sonar, communication system, or the output and input of an amplifier, receiver, or even more complex device.
The Fourier transform F of signals y and x are given by EQU S.sub.y = F{y} EQU S.sub.x = F{x} (1)
from which three power spectra and corresponding time correlations may be computed. These are the cross and auto power spectra and correlations
______________________________________ G.sub.yx = S.sub.y S.sub.x * R.sub.yx = F.sup.-.sup.1 {G.sub.yx} G.sub.yy = S.sub.y S.sub.y * R.sub.yy = F.sup.-.sup.1 {G.sub.yy} G.sub.xx = S.sub.x S.sub.x * R.sub.xx = F.sup.-.sup.1 {G.sub.xx} (2) ______________________________________
Where the asterisk indicates a complex conjugate and F.sup.-.sup.1 is the inverse Fourier transform of the quantity indicated. The correlations and their Fourier transforms are given by
______________________________________ R.sub.yx = .intg.y(t) x(t + .tau.) dt G.sub.yx = F {R.sub.yx} R.sub.yy = .intg.y(t) y(t + .tau.) dt G.sub.yy = F {R.sub.yy} R.sub.xx = .intg.x(t) x(t + .tau.) dt G.sub.xx = F {R.sub.xx} (3) ______________________________________
Signal x is related to the signal y by the transfer function H and impulse response h ##EQU1##
In the foregoing the impulse response h and transfer function H are equivalent statements in the time and frequency domains of the relationship between the signals y and x which may be considered as received and transmitted signals in a receiver or as outputs and inputs of a system under test. In some applications however, the measurement desired is not the relationship between signals but the causality between signals. This type measurement is obtained by computing the coherence function which is given by ##EQU2## where .gamma..sup.2 is a value lying between 0 and 1. In view of equations (4), equation (5) can also be written as follows ##EQU3## which provides an alternative method for computing the coherence function.
It is a well known fact in the radar and communications arts that the output of a linear filter S.sub.y.sbsb.o is related to its input S.sub.y by the filter transfer function H.sub.r EQU S.sub.y.sbsb.o = S.sub.y H.sub.r = G.sub.yx H.sub.r ' (7)
where S.sub.y.sbsb.o and S.sub.y represent the frequency spectra of the output signal y.sub.o and input signal y respectively. The second part of equation (7) is obtained by multiplying and dividing the first part by S.sub.x *.
The output signal y.sub.o may be obtained using any one of the following algorithms
______________________________________ y.sub.o = .intg.y(t) h.sub.r (t - .tau.) dt = .intg.R.sub.yx (t) h.sub.r '(t - .tau.) dt y.sub.o = F.sup.-.sup.1 {S.sub.y H.sub.r } = F.sup.-.sup.1 {G.sub.yx H.sub.r'} y.sub.o = .intg.a(t) y(t - .tau.) dt - .intg.b(t) y.sub.o (t - .tau.) (8) ______________________________________
where the integrals denote finite sums in practice. Thus the output of a filter can be obtained in one of a number of ways; by direct use of the convolution integral in the first of equations (8), by first using equation (7) to obtain the frequency spectrum S.sub.y.sbsb.o and then using the inverse Fourier transform in the second of equations (8), or by using the difference equations in the last of equations (8).
A number of useful ways of designing filters are known in the present filter art including direct convolution, fast convolution, and recursive filtering. In direct convolution the filter is realized by computing the convolution integral, in fast convolution by using the fast Fourier transform (FFT) or chirp-Z transform (CZT) to compute S.sub.y.sbsb.o and then inverse transforming, and in recursive filtering by using linear difference equations. A given filter design can be obtained in a general purpose computer or using special purpose hardware. TABLE 1 is provided showing the number of operations which must be performed when implementing linear filters.
TABLE 1 ______________________________________ DIRECT PROCESSOR CONVO- FAST RECURSIVE TYPE LUTION CONVOLUTION FILTERING ______________________________________ SERIAL N.sup.2 Nlog.sub.2 N NM CASCADE N N N PARALLEL N log.sub.2 N M ARRAY 1 1 1 ______________________________________
where N &gt; M &gt; Nlog.sub.2 N and designations for the processor type indicate the time sequence for performing the operations indicated in the table.
As indicated by TABLE 1 a serial processor performs N.sup.2 operations in time sequence to obtain a direct convolution while fast convolution and recursive filtering reduce the number of operations by factors log.sub.2 N/N and M/N respectively. If the operations are cascaded, paralleled, or arrayed fewer operations are needed and these are obtained in less time but with more software and/or hardware. Thus 1 array operation of an array processor produces the same result at N.sup.2 serial operations in a serial processor to obtain a direct convolution. The execution time of the array processor is therefore the least but its complexity is the greatest since each operation in the array processor requires redundant software and/or hardware which is what is traded for speed. In practice software implementations of the fast convolution, and recursive filtering techniques and with cascading, paralleling, and arraying the operations, has resulted in considerable savings in execution times. As example, if the execution time of a general purpose computer is 1 millisecond/operation then the execution of a serial processor fast convolution is Nlog.sub.2 N milliseconds and this becomes quite large even for modest values of N. Cascading, paralleling, and arraying computers quickly increases the cost. As a consequence, while the general purpose computer has the potential it falls short in many applications which require short execution times and in many other applications which require real time operation. Special purpose hardware is known in the present art having execution times on the order of 1 microsecond/operation and these are indicated for many applications where the processing must be accomplished in real time. FFT hardware has been discussed in the article by Bergland "FFT Transform Hardware Implementations-An Overview" appearing in the June 1969 issue of IEEE Transactions on Audio and Electroacoustics and in the article by Groginsky and Works "A Pipeline Fast Fourier Transform" appearing in the November 1970 issue of IEEE Transactions on Computers. Analog and digital filters are discussed in a number of publications including the article by Squire et al "Linear Signal Processing and Ultrasonic Transversal Filters" appearing in the November 1969 issue of IEEE Transactions on Microwave Theory and Techniques, in the book by Gold and Rader "Digital Processing of Signals" McGraw-Hill 1969, and in the book edited by Rabiner and Rader "Digital Signal Processing" IEEE Press 1972.
It is a well known fact in the present filter art that the number of operations in a filter grows with the number of zeros r and poles m in the filter. Furthermore it is known that non-recursive (zeros only) filters are easy to implement. Because their impulse responses are finite they can be implemented using the fast convolution with result that the number of operations grow only as log.sub.2 r. The computational savings can be impressive when r is large. While recursive (zeros and poles) filters too can be implemented using the fast convolution as well as recursive filtering their impulse response is infinite and they put severe conditions on their implementations with result that the number of operations grows at a rate much higher than log.sub.2 m. As a consequence the computational savings for m large are obtained less efficiently. This can all be seen in the article by Voelcker and Hartquist "Digital Filtering Via Block Recursion" appearing in the reference by Rabiner and Rader. Thus while the non-recursive filter obtains the growth rate log.sub.2 N (r = N ) the recursive filter obtains the rate M &gt; log.sub.2 N (m = N) as shown in TABLE 1. As a consequence while the general purpose computer and special purpose hardware have the potential they both fall short in many applications which require the implementation of a recursive type filter.
A filter is said to be matched when either transfer functions defined by equation (7) satisfy ##EQU4## where .vertline.N.vertline..sup.2 is the power spectrum of the noise or clutter which interferes with the signal y in the filter. The output of a matched filter is obtained by using equation (9) in equation (7)
Examples of matched filters may be obtained by specifying the power spectrum .vertline.N.vertline..sup.2 of the interference in equations (9) and (10); when
______________________________________ ##STR1## H.sub.r = S.sub.x * H.sub.r ' = 1 S.sub.y 0 = G.sub.yx y.sub.o = R.sub.yx (11) ______________________________________
Thus when .vertline.N.vertline..sup.2 = constant, for example thermal noise, the filter is matched for thermal noise when the transfer function H.sub.r is implemented as the complex conjugate S.sub.x * of the signal x and the filter output represents the cross correlation R.sub.yx. This is the most familiar case encountered in practice and has been discussed in a number of publications, for example in chapter 9 in the book by Skolnik "Introduction to Radar Systems" McGraw-Hill 1962. Another important case arises when the interference resembles the signal itself, when ##EQU5## Thus when .vertline.N.vertline..sup.2 = G.sub.xx, the transfer function H.sub.r can be implemented in one of a number of ways as shown in the second of equations (12) and the filter output represents the impulse response h of signals y and x. This case has been discussed in a number of publications, for example in section 12.4 of Skolnik who describes a matched filter for clutter rejection and in the article by Roth "Effective Measurements using Digital Signal Analysis" appearing in the April 1971 issue of IEEE Spectrum. Yet another interesting case arises when the interference resembles the combination of signals, when ##EQU6## Thus when .vertline.N.vertline..sup.2 = (G.sub.yy G.sub.xx).sup.1/2, the transfer function assumes the form shown in the second of equations (13) and the filter output represents the Fourier transform of the square root of the coherence function .gamma..sup.2. This case has been described by Carter et al "The Smoothed Coherence Transform" appearing in the October 1973 issue of IEEE (Lett) Proceedings. In the present disclosure the term "matched filter" will be used to denote a matched filter for thermal noise for which .vertline.N.vertline..sup.2 = constant while the term "matched clutter filter" will denote a matched filter for clutter for which .vertline.N.vertline..sup.2 is a function of frequency.
From the foregoing it can be concluded, first, that once the nature of the interference is specified the matched filter is known, second, the filter can be implemented in any one of a number of ways using equations (8) and, third, the matched filter is a non-recursive (zeros only) type filter while the matched clutter filter is a recursive (zeros and poles) type filter. As a consequence, it is to be expected that the matched filter is a simple apparatus based on R.sub.yx and G.sub.yx while the matched clutter filter is a complex apparatus based on h and H or .GAMMA. and .gamma..
The matched filter based on R.sub.yx and G.sub.yx is useful in many practical applications especially where there exists little or no interference except thermal noise and signal y almost identically therefore resembles signal x. The matched clutter filter based on h and H is useful when the interference resembles signal x and signal y is a complex signal, for example a group or plurality of closely spaced overlapping signals each signal in the group being almost identical to signal x. The matched clutter filter based on .GAMMA. and .gamma. is useful when the interference resembles the product of signals y and x, for example when both signals y and x have been mixed.
The problem at hand is to obtain a better measurement of the time delay and frequency relationships of signals y and x in a clutter environment. Such measurements are needed in applications involving the arrival of multiple closely spaced and overlapping signals y following transmission of a signal x, for example in radar, sonar, and communications applications and in applications involving the frequency response of a system under test, for example a communication line, an amplifier and so forth. In such applications the measurement of the impulse response h and its transfer function H ##EQU7## have better time resolution and frequency response than the cross correlation R.sub.yx and its power spectrum G.sub.yx
______________________________________ R.sub.yx = .intg.G.sub.yx .sup.ej.omega.t d.omega. G.sub.yx = F{R.sub.yx} (15) ______________________________________
The better measurements afforded by equation (14) over equation (15) are obtained by dividing the cross power spectrum G.sub.yx by the auto power spectrum G.sub.xx or, alternatively in view of equation (4), by dividing the frequency spectrum S.sub.y by the frequency spectrum S.sub.x. This is the problem discussed both by Skolnik and Roth. It has also been suggested ad hoc by Carter et al that an even better result is obtained by dividing the cross power spectrum G.sub.yx by the square root of the product of auto correlations (G.sub.yy G.sub.xx).sup.1/2. As discussed previously, the whitening process of dividing the cross power spectrum G.sub.yx by the power spectrum .vertline.N.vertline..sup.2 of the interference results in a matched filter for the particular type of interference which is being specified in the matching.
The benefits which are to be derived from the measurement of the impulse response h, transfer function H, and coherence function .gamma..sup.2 are threefold; first, it becomes possible to unambiguously determine the time delay between signals even though the signals may have complex shapes or forms, components, codings, close arrival spacings of components and overlappings, second, it becomes possible to accurately determine the performance of a system under test, and third, it becomes possible to determine the effect of noise. To achieve these three important situations the present art proceeds in a certain sequence of steps; first it obtains the transfer function H.sub.r of the filter in one of three canonical forms (direct, cascade, parallel) then obtains the filter architecture. Unfortunately however the procedure is limited since the system errors, especially the input quantization and transfer function quantization errors, impose severe restrictions upon the physical implementations of the filter, which for the particular case of a filter with a large number of poles results in a highly inefficient and uneconomic apparatus in the present art. As will become apparent during the course of the disclosure the present invention overcomes these serious deficiencies in the present filter art by implementing the recursive filter as a matched clutter filter. In general, computations of the convolution integral can be made using general purpose computers or using special purpose hardware with the latter offering significant savings in computational speeds and costs in a large number of applications. However, while the design of a matched filter involves the relatively simple problem of designing a filter having no poles and only zeros, the corresponding design of a matched clutter filter involves the increasingly difficult problem of designing a filter having both poles and zeros and this reflects directly in the weight, size, power consumption, and cost of both the software and hardware which may be used. Matched clutter filters are therefore more complex and costly devices when compared to simple matched filters and for this reason are not generally available for mass consumption and use. In fact the design of a matched clutter filter for real time operation becomes almost prohibitive since a large amount of paralleling of elemental hardware building blocks becomes necessary in order to achieve the desired speedup of the signal processing throughput. This can all be seen in the article by Bergland.
From the foregoing it is clear that making the needed computations using special purpose hardware offers the potential benefit of high speed processing but while this is easily said it is not easily done. The fact is that recursive filters are complex and costly devices and have not found extensive use in practice. Thus while the present art has the potential it has failed to provide simple and economic apparatus and method for implementing recursive filters, for example for computing the impulse response h, transfer function H, and coherence function .gamma..sup.2.
What is important in the decision to implement a matched clutter filter is the accuracy and ambiguity which can be tolerated in the desired result. As example, many applications can be satisfied with a simple matched filter comprising a single correlator and a single Fourier analyzer to obtain the cross correlation R.sub.yx and cross power spectrum G.sub.yx from which the relationship between signals y and x may be obtained to within some low but tolerable accuracy and ambiguity. If higher accuracy and less ambiguity are desired in the application then a complex matched filter must be implemented comprising perhaps a number of correlators and Fourier analyzers to obtain the impulse response h and transfer function H. In practical terms the desire for higher accuracy and less ambiguity requires the whitening process of dividing the cross power spectrum G.sub.yx by the auto power spectrum G.sub.xx as discussed in the article by Roth or, in some applications, dividing the cross power spectrum G.sub.yx by the square root of the product of auto power spectra (G.sub.yy G.sub.xx).sup.1/2 as discussed by Carter et al. Thus the accuracy and ambiguity resolution which is required in a given application will determine the degree and type of whitening which is required in the application and consequently will determine the complexity of the apparatus which is to be used. In general, the measurement of the impulse response h based upon the whitened cross power spectra G.sub.yx /G.sub.xx or G.sub.yx /(G.sub.yy G.sub.xx).sup.1/2 is a more complex measurement than is the measurement of the cross correlation R.sub.yx based upon the unwhitened cross power spectrum G.sub.yx and consequently the apparatus of the matched clutter filter is more complex than that for the matched filter.
Once the selection of the whitening process is made in a given application the problem reduces to the implementation of apparatus having the highest possible speed and lowest possible weight, size, power consumption and cost. In general the transforms represented by equations (8) present an excessive computational load for a general purpose computer and a heavy load even for a digital computer structured for signal processing. For example, a straightforward linear transformation in a computer that takes a sequence of N data points into a sequence of N transform points may be regarded as a multiplication by a vector N.sup.2 matrix. A direct implementation therefore requires N.sup.2 words of storage and N.sup.2 multipliers (simultaneous multiplications). However it is well known that in a correlation or convolution integral one can take advantage of the fast Fourier transform algorithm (FFT) which requires only about Nlog.sub.2 N calculations instead of N.sup.2 and for N large the time and storage space saved becomes quite significant. This can all be seen in the article by Stockham "High Speed Convolution and Correlation" appearing in the 1966 Spring Joint Computer Conference AFIPS Conf Proc vol 28, Washington, DC; Spartan pp 229-233.
Matched filters, correlators, and convolvers for performing the computations of matched filtering, cross and auto correlation, and convolution are known in the art which require only 2N words of storage and N multipliers. These make their computations in the time domain and are discussed in a number of publications including the paper by Whitehouse et al "High Speed Serial Access Linear Transform Implementations" Naval Undersea Center, San Diego, CA 92132 January 1973. In general apparatus fall into two broad categories; those employing acoustic means and non-acoustic means. Included in the former category are sonic, magnetostrictive, acoustic surface waves, and opto-acoustic filters while the latter category comprises charge coupled devices (CCD), binary shift registers (BSR), and random access memories (RAM). Acoustic filters have been described in the paper by Squire et al "Linear Signal Processing and Ultrasonic Transversal Filters" appearing in the November 1969 issue of IEEE Transactions on Microwave Theory and Techniques and in the paper by Holland and Claiborne "Practical Acoustic Wave Devices" appearing in the May 1974 issue of IEEE Proceedings while non-acoustic filters have been described in the paper by Byram et al "Signal Processing Device Technology" appearing in the Proceedings of the NATO Advanced Study Institute on Signal Processing held at the University of Technology, Loughborough, U.K. on Aug. 21 through Sept. 1, 1972, and in the papers by Kosonocky and Buss et al appearing in Technical Session 2 "Introduction to Charge Coupled Devices" 1974 Wescon, Los Angeles Sept. 10 through 13, 1974. In particular, digital implementations for matched filters, correlators, and convolvers have been disclosed in my copending applications Ser. Nos. 595,240 filed July 11, 1975 (a continuation-in-part of 450,606 filed Mar. 13, 1974, now abandoned and 479,872 filed June 17, 1974 now U.S. Pat. No. 3,950,635.
Fourier analyzers for performing the computations of the Fourier transform and inverse Fourier transforms are well known in the present art. These make their computations generally in the frequency domain and employ all-software or all-hardware logic to make the computations using the Fast Fourier Transform (FFT). While software devices using FFT offer a decided advantage over a non FFT computer in that they require Nlog.sub.2 N words of storage and Nlog.sub.2 N multipliers they do not possess the simplicity of their counterpart time domain computers and special purpose FFT hardware. FFT special purpose hardware are known in the present art having only 2N words of storage and N multipliers and these have been described in the article by Bergland "FFT Hardware Implementations -- an Overview" appearing in the June 1969 issue of IEEE Transactions on Audio and Electroacoustics and in the article by Groginsky and Works "A Pipeline FFT" appearing in the November 1970 IEEE Transactions on Computers. Hardwired time compression Fourier analyzers are also known in the present art and these are described in Report TB-11 "Real Time -- Time Compression Spectrum Analysis" 1971 Signal Analysis Corporation, Hauppauge, NY 11787, and in Monograph No. 3 "Real Time Signal Processing in the Frequency Domain" 1973 Federal Scientific Corporation, New York, NY 10027. Fourier analyzers are compared in Planning Report No. 23 "Comparison of FFT Analyzers" Revised April 1973 Federal Scientific Corporation. In particular, a digital implementation for a FFT processor has been disclosed in my copending application Ser. No. 520,748 filed Nov. 4, 1974 now U.S. Pat. No. 3,965,342.
From the foregoing it is clear that while the present art provides high speed efficient method and apparatus for implementing matched filters it falls short of providing such method and apparatus for implementing matched clutter filters. The situation is particularly frustrating in signal processing applications in which it is desired to obtain the impulse response h, transfer function H, and coherence function .gamma..sup.2 for a pair of complex signals. By making most computations in error sensitive apparatus, the present art is burdened by low computational speeds and apparatus having large weight, size, power consumption, and cost. To conserve investments in applications for which speed can be traded the present art achieves savings by making computations off-line, i.e., not in real time (storing signals and using conventional computers).
From this discussion it is clear that in the past the implementation of a system for the measurement of the impulse response h, transfer function H, and coherence function .gamma..sup.2 has been accomplished primarily using error sensitive devices and for all practical purposes has not been made commercially available to any great extent being confined to the laboratory and to certain industrial and governmental applications where performance is required at any cost.
It is the purpose of the present invention to produce a matched clutter filter for the measurement of the impulse response h, transfer function H, and coherence function .gamma..sup.2 which operates in real time and in many applications betters the efficiency and economy of apparatus used in the present art.